#ifndef __MY_STACK_H__
#define __MY_STACK_H__
#include <iostream>
#include "global.h"

using namespace std;

template <class Type>
class MyStack {
public:
	// constructor
	MyStack();

	// copy constructor
	MyStack(MyStack<Type> &s);

	~MyStack();

	Type top();
	Type min();
	bool pop();
	bool push(Type elem);
	bool empty();
	bool clear();
	size_t size();
	bool print();

private:
	void removeLinkList(NODE<Type> *head);
	bool addNode(NODE<Type> *&head, Type val);

	NODE<Type> *head;
	NODE<Type> *head_min;
	size_t node_num;
};


template<class Type> 
MyStack<Type>::MyStack() {
	head = NULL;
	head_min = NULL;
	node_num = 0;
}

template<class Type>
MyStack<Type>::MyStack(MyStack<Type> &s) {
	// Initialization
	head = NULL;
	head_min = NULL;
	node_num = 0;

	// If there is any node in the input stack
	// copy the value to the new stack. Note that
	// the first node popped out should be the head
	// and the last node popped out needs to be in
	// the bottom
	// At the same time, we should change the content of
	// the input stack. 
	NODE<Type> *in_node, *node, *last_added_node;
	in_node = s.head;
	while (in_node) {
		node = (NODE<Type> *)malloc(sizeof(NODE<Type>));
		memset(node, 0, sizeof(NODE<Type>));
		node->val = in_node->val;
		if (head == NULL) {
			head = node;
			last_added_node = node;
		}
		else {
			last_added_node->next = node;
			last_added_node = node;
		}
		in_node = in_node->next;
		++node_num;
	}

	// copy the min value link list, which also need to be
	// in the reverse order. In another word, each node is
	// added in the tail of the link list
	in_node = s.head_min;
	while (in_node) {
		node = (NODE<Type> *)malloc(sizeof(NODE<Type>));
		memset(node, 0, sizeof(NODE<Type>));
		node->val = in_node->val;
		if (head_min == NULL) {
			head_min = node;
			last_added_node = node;
		}
		else {
			last_added_node->next = node;
			last_added_node = node;
		}
		in_node = in_node->next;
	}	
}

template<class Type>
void MyStack<Type>::removeLinkList(NODE<Type> *head) {
	NODE<Type> *node;
	while (head) {
		node = head;
		head = head->next;
		free(node);
	}

	return;
}

template<class Type>
bool MyStack<Type>::addNode(NODE<Type> *&head, Type val) {
	NODE<Type> *node = (NODE<Type> *)malloc(sizeof(NODE<Type>));
	if (node == NULL) {
		cout << "Allocate node buffer error, NULL!" << endl;
		return false;
	}

	memset(node, 0, sizeof(NODE<Type>));
	node->val = val;
	node->next = head;
	head = node;

	return true;
}

template<class Type> 
MyStack<Type>::~MyStack() {
	removeLinkList(head);
	removeLinkList(head_min);

	node_num = 0;
}

template<class Type> 
bool MyStack<Type>::push(Type val) {
	bool ret_val;
	ret_val = addNode(head, val);
	if (!ret_val) {
		cout << "Add node error!" << endl;
		return false;
	}
	++node_num;

	if (head_min == NULL || 
		val <= head_min->val) {
		ret_val = addNode(head_min, val);
		if (!ret_val) {
			cout << "Add node error!" << endl;
			return false;
		}
	}

	return true;
}

template<class Type> 
Type MyStack<Type>::top() {
	if (head == NULL) {
		cout << "Error, empty stack!" << endl;
		return (Type)0;
	}

	return head->val;
}

template<class Type>
Type MyStack<Type>::min() {
	if (head_min == NULL) {
		cout << "Error, empty stack!" << endl;
		return (Type)0;
	}

	return head_min->val;
}

template<class Type> 
bool MyStack<Type>::pop() {
	if (head == NULL) {
		cout << "Error, empty stack!" << endl;
		return false;
	}

	NODE<Type> *node = head;
	NODE<Type> *node_min = head_min;
	if (node_min->val == head->val) {
		head_min = head_min->next;
		free(node_min);
	}

	head = head->next;
	free(node);
	--node_num;

	return true;
}

template<class Type> 
bool MyStack<Type>::empty() {
	if (head == NULL) {
		return true;
	}
	else {
		return false;
	}
}

template<class Type>
bool MyStack<Type>::clear() {
	removeLinkList(head);
	removeLinkList(head_min);

	node_num = 0;

	return true;
}

template<class Type>
size_t MyStack<Type>::size() {
	return node_num;
}

template<class Type>
bool MyStack<Type>::print() {
	if (node_num <= 0) {
		return false;
	}

	Type *elem_ptr = (Type *) malloc(sizeof(Type) * node_num);
	if (elem_ptr == NULL) {
		cout << "Allocate buffer error, NULL!" << endl;
		return false;
	}

	size_t i;
	NODE<Type> *node;
	node = head;
	for (i = 0; i < node_num; i++) {
		if (node) {
			elem_ptr[i] = node->val;
			node = node->next;
		}
		else {
			cout << "Error, NULL node!" << endl;
			return false;
		}
	}

	cout << "Stack content: ";
	for (i = 0; i < node_num; i++) {
		cout << elem_ptr[node_num - 1 - i] << "\t";
	}
	cout << endl;

	free(elem_ptr);

	return true;
}

#endif

